May 3, 2016

Random graph stuff

Preliminaries and notation

  • A graph \(G\) is a mathematical object that consists of a set of vertices (nodes), \(V(G)\) and a set of edges (links), \(E(G)\). Let \(e_{ij} \in E(G)\) denote the edge between vertices \(i, j \in V(G)\).
  • Throughout, \(n = |V(G)|\) is the number of vertices in \(G\) and \(e = |E(G)|\) the number of edges.
  • The degree of vertex \(i \in V(G)\), \(d_i\) is the number of edges that are connected to vertex \(i\).
  • We consider undirected (\(e_{ij} = e_{ji}\)) and loopless (\(i \not= j \forall e_{ij} \in E(G)\)) graphs.
  • The distance \(dist(i, j)\) is the minimum number of edges in a connected path from \(i\) to \(j\) in \(G\).
  • The \(d\)th order neighborhood of a vertex \(i \in V(G)\) is defined as \(N_d(u, G) = \{j \in V(G): dist(i, j) \le d\}\)

Neighborhoods

d =

(Martin 2011, Cukier (2012))

Network inference

A complete description of a network and its topology is infeasible \(\Rightarrow\) we can study the statistics of a complex network (i.e., clustering coeffients, numbers of triangles, average degree, etc.)

Let

  • \(G\) be a hypothetical undirected random graph,
  • \(F = \{f(k), k \ge 0\}\) the degree distribution of \(G\),
  • \(G_n\) be an observed realization of \(G\) of order \(n\) s.t. as \(n \rightarrow \infty\), the joint degree distributions of \(G_n\) approach the joint degree distribution of \(G\).
  • \(d_1, \dots, d_n\) be the observed degrees of the vertices in \(G_n\).

Goal: Estimate some statistic \(T_n\) of \(G\) using a block bootstrap.

A snowball's chance…

Overview

  • "Using the bootstrap for statistical inference on random graphs", Thompson, et. al. (2016); snowboot package on CRAN
  • Estimation of mean degree of \(G\), \(T_n = \mu(G)\), from a sample of vertices using a patchwork sampling method - "labelled snowball sampling with multiple inclusions (LSMI)", from survey sampling
  • seeds \(=\) initial random sample of single vertices
    patch \(=\) formed by following paths of connected vertices emanating from the seed up to a certain distance
    wave \(=\) increments in distance
  • The degrees of all vertices visited in a patch are observed
  • bootstrap seeds (randomly sample seeds with replacement and estimate the mean degree) then non-seeds (non-weighted or weighted selection proportional to reciprocals of their degrees); repeat \(T \times B\) bootstrap replications.

Sampling Algorithm

Data: graph \(G_n\); number of seeds \(m\), \(m < n\); number of waves \(d\)
Result: sample of \(m\) seeds with \(d\) waves around each seed.
seed \(=\) randomly sample without replacement \(m\) vertices from \(G_n\)
for \(q = 1, \dots, m\) do
    start with original \(G_n\) and \(seed_q\)
    for \(w = 1, \dots, d\) do
        \(wave_w =\) select all immediate neighbors using the existing edges
        remove the used edges
    end
    \(patch_q =\) join the current \(seed_q\) and all \(wave_w\) keeping the repeated elements
end
join all \(m\) patches, keeping all of the repeated elements

Additionally, sample non-seeds according to non-weighted or weighted selection.

Repeat \(B\) times and calculate the estimate, \(T_n^*\) for each replicate.

Note: The authors recommend running this procedure \(T\) times to get \(T\) bootstrap distributions because high variability among LSMIs

Estimator

\[T_n^* = \frac{\dfrac{1}{m}\sum_{q=1}^{m}d_q + D(1-\hat{p}_0)\dfrac{1}{m}\sum_{q=1}^m \tilde{A}_{NSq}}{\dfrac{1}{m}\sum_{q=1}^m 1 + D\dfrac{1}{m}\sum_{q=1}^m \tilde{B}_{NSq}}\]
Where

  • \(\hat{p}_0\) is the relative frequency of vertices of degree zero among the seeds,
  • \(D\) is an arbitrary conbination factor depending on the degree distribution, for simplicity set \(D =\) the average degree of seeds.
  • \(\tilde{A}_{NSq}\) and \(\tilde{B}_{NSq}\) are the wave-combined Horwitz-Thompson estimators of the sum of the degrees of all vertices in \(G_n\) and the number of vertices in \(G_n\) having positive degree, respectively.
    \[\tilde{A}_{NSq} = \sum\limits_{w = 1}^d \sum\limits_{j \in \text{ wave } w \text{ of } q} 1 \text{ and } \tilde{B}_{NSq} = \sum\limits_{w = 1}^d \sum\limits_{j \in \text{ wave } w \text{ of } q} \frac{1}{d_j}\]

Properties

Conditions:

  1. The size of a \(d\)-wave patch has its third absolute moment bounded above in probability.
  2. The variances of both the size of a \(d\)-wave patch and the number of non-seeds per first neighbor for a \(d-\)wave patch are bounded below in probability.
  3. The expectaion of the excess degree of each neighbor of a random seed is independent of the degree of the seed (to order \(o_p(1)\))

Theorem:

  1. Suppose that the degree distribution of \(G\) has a positive variance and a finite fourth moment. Also suppose that under the mechanism generating a degree sequence and \(G_n\), C1 and C2 are satisfied. Then the LSMI estimator is asymptotically normal as \(n\) and \(m\) tend to \(\infty\) with \(m \le n/2\).
  2. If either \(d = 1\) or \(d > 1\) and C3 holds, then the LSMI estimator is consistent for the mean degree of G.

This is complicated


  • Variability among LSMIs is high - due to sampling scheme being variable?
  • How does the variance of the estimator compare to the expected variance? (Does this even really work?)
  • How do we reconcile these \(T\) bootstrap distributions?
  • Tuning - have to choose a seed-wave (\(w\) and \(d\)) combination, choice of two tuning parameters, which may also have sensitivy to interaction effects.
  • Extensibility - how hard is it to extend this to other statistics?

Here's an idea…

Something simpler

Let's try to estimate \(T_n =\) the # of edges in \(G\) \(= e\) to start.

Algorithm

Data: graph \(G_n\); average block size, \(m = \frac{1}{n}\sum\limits_{i =1}^n \{d_i + 1\}\); number of blocks, \(k = \lfloor\frac{n}{m}\rfloor\); intra-block connection probability, \(\hat{p}\).
Result: \(B\) estimates of \(T_n\)
for \(i = 1, \dots, B\) do
    start with original \(G_n\), select \(k\) indices \(j \in 1, \dots, n\) with replacement.
    for \(j = 1, \dots, k\) do
        \(B_j =\) select all vertices \(k \in N_1(j)\) and vertex \(j\), keeping all the existing edges
    end
    join the disconnected subgraphs (\(B^*_1, \dots, B^*_k\)) via iid \(Bern(\hat{p})\) draws. The result is \(G^*_i\).
    Calculate \(T_n^*\) for \(G^*_i\).
end

\[T_n^* = |E(G^*_i)| = e^*_i\]

Properties

\(\hat{p} = \frac{2(m - 2)e}{nm(n-m)}\)

See Appendix for details.

Simulated examples

Thoughts

  • Could extend this procedure using a tuning parameter, \(d\), the distance to define a block.
    • Currently, \(d = 1\). Would need to adjust \(\hat{p}\) and \(m\) accordingly.
    • This could be useful for different statistics \(T_n\) that we are interested in (like number of triangles, mean degree, etc.)
  • Variance properties/asymptotics unclear
  • Compare to LSMI (would need corresponding \(\hat{p}\) for unbiased estimate of \(\mu(G)\))

Appendix

Property details

References

Cukier, Jerome. 2012. “Events in the Game of Thrones.” December. http://www.jeromecukier.net/projects/agot/events.html.

Martin, George RR. 2011. A Dance with Dragons. New York, NY, USA: Bantam Books.

Thompson, Mary E., Lilia L. Ramirez Ramirez, Vyacheslav Lyubchich, and Yulia R. Gel. 2016. “Using the Bootstrap for Statistical Inference on Random Graphs.” Canadian Journal of Statistics 44 (1): 3–24.